#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include<string.h>

void printPartition(int * arr,int length){

    int ind;
    for(ind = 0;ind < length -1; ind++){

        printf("%d + ",arr[ind]);
    }
    printf("%d\n",arr[length-1]);
}
void partition(int * arr,int ind,int left){

    int val;
    if(left == 0){

        printPartition(arr,ind);
        return;
    }
    for(val = 1;val <= left;val++){

        arr[ind] = val;
        partition(arr,ind + 1,left - val);  // f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5) + ..... + f(1) + 1
    }
}

// f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5) + ..... + f(1) + 1
// f(n-1) =        f(n-2) + f(n-3) + f(n-4) + f(n-5) + ..... + f(1) + 1
// f(n) = 2f(n-1)
// f(n-1) = 4f(n-2)
// f(n-2) = 8f(n-3)
// ...
// f(1) = 2^(n-1)f(n - (n - 1))
int totalCount(int n){

    if(n == 0){

        return 1;
    }
    int sum = 0;
    for(int i = 1; i <= n;i++){

        sum += totalCount(n-i);
    }
    return sum;
}


int
main(int argc,char * argv[]){

    if(argc != 2){

        return EXIT_FAILURE;
    }
    int n = (int)strtol(argv[1],NULL,10);
    if(n < 0){

        printf("need one position integer.\n");
        return EXIT_FAILURE;
    }
    int * arr = (int*)malloc(sizeof(int) * n);
    partition(arr,0,n);
    free(arr);
    int sum = totalCount(n);
    printf("total count = %d.\n",sum);
    return EXIT_SUCCESS;
}